﻿// homework5_problem3.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


#include<iostream>
#include<algorithm>
using namespace std; 
void merge(int *data,int start,int end,int *result) {    
	int left_length = (end - start + 1) / 2 + 1;        
	int left_index = start;    
	int right_index = start + left_length;    
	int result_index = start;    
	while(left_index<start + left_length && right_index <end + 1)     
	{        
		if(data[left_index] <= data[right_index])            
			result[result_index++] = data[left_index++];        
		else            
			result[result_index++] = data[right_index++];    
	}   
	while(left_index < start + left_length)        
		result[result_index++] = data[left_index++];    
	while(right_index <end+1)        
		result[result_index++] = data[right_index++];
} 

void merge_sort(int *data,int start,int end,int *result){    
	if(1 == end - start)    
	{        
		if(data[start] > data[end])        
		{            
			int temp = data[start];            
			data[start] = data[end];            
			data[end] = temp;       
		}        
		return;    
	}    
	else if (end == start)        
		return;   
	else{             
		merge_sort(data, start, (end - start + 1) / 2 + start, result);        
		merge_sort(data, (end - start + 1) / 2 + start + 1, end, result);         
		merge(data, start, end, result);        
		for (int i = start; i <= end;++i)        
		{            
			data[i] = result[i];        
		}    
	} 
}
int main(){    
	int length;
	//printf("输入元素个数\n");
	scanf("%d", &length);//记得改成scanf
	int data[100];
	for (int i = 0; i < length; i++) {
		scanf("%d", &data[i]);
	}
	int result[100];     
	merge_sort(data, 0, length - 1, result);    
	for (int i = 0; i < length;i++)        
		cout << result[i]<<' ';    
	return 0;
}


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
